package com.whitedust.top40;

import java.util.ArrayList;
import java.util.List;

/**
 * @author A
 * @since 2025/11/5 10:36
 */

public class Top34 {
    public List<String> restoreIpAddresses(String s) {
        List<Integer> path = new ArrayList<>();
        List<String> res = new ArrayList<>();
        partition(s, 0, path, res);
        return res;
    }

    private boolean isValid(String s) {
        if (s == null || s.isEmpty()) return false;
        if (s.length() > 1 && s.charAt(0) == '0') return false;
        if (s.length() > 3) return false;
        int num = Integer.parseInt(s);
        return num >= 0 && num <= 255;
    }

    public void partition(String s, int k, List<Integer> path, List<String> res) {
        if (path.size() == 4 && k == s.length()) {
            StringBuffer sb = new StringBuffer();
            for (int num : path) {
                sb.append(num);
                sb.append(".");
            }
            sb.deleteCharAt(sb.length() - 1);
            res.add(sb.toString());
        }
        for (int i = k; i <= s.length() - 1; i++) {
            String substring = s.substring(k, i + 1);
            if (isValid(substring)) {
                path.add(Integer.valueOf(substring));
                partition(s, i + 1, path, res);
                path.remove(path.size() - 1);
            } else break;
        }
    }


}

